# 类名称：DElemType
# 类说明：数据元素类型
# 类释义：该类拥有带排序的关键字key和值value
class DElemType:
    def __init__(self, key):
        self.key = key


# 类名称：BSTNode
# 类说明：定义一个二叉排序树的结点
# 类释义：分别有数据元素data,左孩子Left和右孩子Right

# 二叉排序树结点的定义
class BSTNode:
    def __init__(self, data):
        self.data = data
        self.Left = None
        self.Right = None


# 类名称：BSTree
# 类说明：定义一个二叉排序树
# 类释义：
class BSTree:
    def __init__(self):
        self.root = None
        for i in range(len(node_list)):
            self.InsertNode(node_list[i])

    # 插入结点函数
    def InsertNode(self, key):
        bt = self.root
        if not bt:
            self.root = BSTNode(DElemType(key))
            return
        while True:
            if key < bt.data.key:
                if not bt.Left:
                    bt.Left = BSTNode(DElemType(key))
                    return
                bt = bt.Left
            elif key > bt.data.key:
                if not bt.Right:
                    bt.Right = BSTNode(DElemType(key))
                    return
                bt = bt.Right
            else:
                bt.data.key = key
                return

    # 创建二叉排序树函数
    def CreateTree(self, node_list):
        for i in range(len(node_list)):
            self.InsertNode(node_list[i])

    # 二叉排序树的查找函数
    def SearchBST(self, root, key):
        if not root:
            return
        elif root.data.key == key:
            return root
        elif root.data.key < key:
            return self.SearchBST(root.Right, key)
        else:
            return self.SearchBST(root.Left, key)

    # 中序遍历
    def Visit(self, root):
        if not root:
            return
        self.Visit(root.Left)
        print(root.data.key)
        self.Visit(root.Right)


# 主程序
node_list = [4, 9, 11, 25, 3, 12, 17, 1, 32, 20, 15]
BST = BSTree()
BST.CreateTree(node_list)
BST.Visit(BST.root)
while True:
    iKey = input("请输入待查找关键字(#退出):")
    if iKey == '#':
        break
    BSTKey = int(iKey)
    P = BST.SearchBST(BST.root, BSTKey)
    if not P:
        print("在二叉排序树中未找到关键字", BSTKey)
    else:
        print("在二叉排序树中找到关键字", P.data.key)